public class LongestPalindrome {
    // leetcode 最长回文子串
    // https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
    public String longestPalindrome1(String s) {
        int maxLength = -1, startIndex = -1, endIndex = -1;
        int len = s.length();
        // dp数组表示以i开始，j结尾的字符串是否为回文子串
        // 因为需要使用到dp[i+1][j-1]，所以填表顺序为从下往上、从左到右
        boolean[][] dp = new boolean[len][len];
        for (int i = len-1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;
                    if (dp[i][j]) {
                        if (j - i + 1 > maxLength) {
                            maxLength = j - i + 1;
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }
            }
        }
        return s.substring(startIndex, endIndex+1);
    }

    /**
     * 空间优化
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int maxLength = -1, startIndex = -1, endIndex = -1;
        int len = s.length();
        // dp数组表示以i开始，j结尾的字符串是否为回文子串
        // 因为需要使用到dp[i+1][j-1]，所以填表顺序为从下往上、从左到右
        boolean[] dp = new boolean[len];
        for (int i = len-1; i >= 0; i--) {
            // 因为填表顺序是从下往上、从左往右的
            // 所以在填dp[i-1]的时候就会将dp[i+1][j-1]的位置覆盖，所以就需要使用prev变量将dp[i+1][j-1]的值记录下来
            // prev记录dp[i+1][j-1]的值
            boolean prev = true;
            for (int j = i; j < len; j++) {
                boolean tmp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = i+1 < j ? prev : true;
                    if (dp[j]) {
                        if (j - i + 1 > maxLength) {
                            maxLength = j - i + 1;
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }else {
                    dp[j] = false;
                }
                prev = tmp;
            }
        }
        return s.substring(startIndex, endIndex+1);
    }
}
